// https://www.lintcode.com/problem/longest-common-subsequence/description
// 打印路径


class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &A, string &B) {
        if (A.empty() || B.empty())
            return 0;
        int n = A.length();
        int m = B.length();
        vector<vector<int>> res(n + 1, vector<int>(m + 1));
        vector<vector<int>> rec(n + 1, vector<int>(m + 1));
        
        for (int i = 0; i < n + 1; ++i)
        {
            for (int j = 0; j < m + 1; ++j)
            {
                if (i == 0 || j == 0)
                {
                    res[i][j] = 0;
                    continue; //别忘了！
                }
                res[i][j] = max(res[i][j - 1], res[i - 1][j]);
                if (res[i][j] == res[i][j - 1])
                    rec[i][j] = 1;
                else 
                    rec[i][j] = 2;
                // if (A[i - 1] == B[i - 1])
                if (A[i - 1] == B[j - 1])
                {
                    res[i][j] = max(res[i][j], res[i - 1][j - 1] + 1);
                    if (res[i][j] == res[i - 1][j - 1] + 1)
                        rec[i][j] = 3;
                }
            }
        }
        
        vector<char> path(res[n][m]);
        int p = res[m][n] - 1;
        int i = n;
        int j = m;
        while (i > 0 && j > 0)
        {
            if (rec[i][j] == 3)
            {
                path[p] = A[i - 1];
                i--;
                j--;
                p--;
            }
            else if (rec[i][j] == 2)
                i--;
            else
                j--;

        }
        for (int i = 0; i < res[m][n]; ++i)
        {
            cout << path[i] << " " << endl;
        }
        return res[n][m];
    }
};